package 布隆过滤器;

import java.util.BitSet;

/**
 * @author chedx
 * @data 2021/3/22 3:23 PM
 */
public class MyBloomFilter {

    //位数组默认大小
    private static final int DEFAULT_SIZE = 2 << 24;
    // hash函数的种子
    private static final int[] SEEDS = new int[]{3, 13, 46};

    private BitSet bits = new BitSet(DEFAULT_SIZE);

    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    public MyBloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    public void add(Object value) {
        for(SimpleHash f : func) {
            bits.set(f.hash(value),true);
        }
    }

    public boolean containsKey(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
            if(!ret) {
                return ret;
            }
        }
        return ret;
    }





    public static class SimpleHash {
        private int cap;
        private int seed;
        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h =
                    value.hashCode()) ^ (h >>> 16)));
        } }
}
